class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> solution;
        if (nums.empty()) {
            return solution;
        }
        sort(nums.begin(), nums.end());
        vector<int>::iterator i = nums.begin();
        while (i < nums.end()-2) {
            int sum = -*i;
            vector<int>::iterator j = i+1;
            vector<int>::iterator k = nums.end()-1;
            
            while (j < k) {
                if (*j + *k < sum) {
                    j++;
                } else if (*j + *k > sum) {
                    k--;
                } else {
                    vector<int> triplet = {*i, *j, *k};
                    solution.push_back(triplet);
                    while (j < k && *j == *++j);
                    while (j < k && *k == *--k);
                }
            }
            while (i < nums.end()-2 && *i == *++i);
        }        
        return solution;
    }
};
